1. Field of the Invention
The present invention relates to efficient distribution of routing information in a mobile ad hoc network. In particular, the present invention relates to forwarding packets in a mobile ad hoc network that utilizes reactive routing protocols for route discovery, where the packets are forwarded in a manner that minimizes the transfer of routing information between nodes in the mobile ad hoc network during packet transmission.
2. Description of the Related Art
Mobile computing has evolved to an extent that it is no longer limited to a mobile computing model (e.g., “Mobile IP”) that relies a fixed wide area network infrastructure such as the Internet to provide connectivity between a mobile node and a correspondent node; rather, a mobile ad hoc network (MANET) model has been pursued that enables an isolated group of mobile nodes to independently establish communications among each other (e.g., a “mesh”) and establish optimized routing paths among each other.
The MANET model has been developed based on numerous proposals by Internet Engineering Task Force (IETF) groups: these IETF proposals (e.g., Requests for Comments (RFCs), Internet Drafts, etc.) have addressed improved mobility support of mobile devices (e.g., laptops, IP phones, personal digital assistants, etc.) in an effort to provide continuous connectivity between mobile ad hoc nodes.
The MANET model assumes no previous existing network topology: Internet connectivity is neither assumed nor precluded, and every network node is assumed to be mobile. Consequently, the MANET model assumes no more than a group of mobile nodes (e.g., mobile hosts and mobile routers) may arbitrarily connect to each other via available link layer (“Layer 2”) connections, resulting in a mesh network.
The IETF has a Mobile Ad-hoc Networks (MANET) Working Group that is working to implement this ad hoc networking model by developing standardized MANET routing specification(s) for adoption by the IETF. According to the MANET Working Group, the “mobile ad hoc network” (MANET) is an autonomous system of mobile routers (and associated mobile hosts) connected by wireless links—the union of which form an arbitrary graph. The routers and hosts are free to move randomly and organize themselves arbitrarily; thus, the network's wireless topology may change rapidly and unpredictably. Such a network may operate in a standalone fashion, or may be connected to the larger Internet.
The MANET system is particularly suited to low-power radio networks that may exhibit an unstable topology, where wireless propagation characteristics and signal quality between a wireless transmission source and a receiver can be difficult to model and quantify. Since there is no fixed network infrastructure in a MANET, the device address is tied to the device, not a topological location. Hence, the formation of a MANET based on mobile nodes having established a mesh network raises issues as to whether a routing protocol should be deployed that provides network layer (“Layer 3”) connectivity throughout the mesh network based on established routes.
For example, a proactive routing protocol (e.g., Open Shortest Path First (OSPF) as specified by RFC 1583) enables mobile routers in the MANET to distribute routing information among each other to create optimized network layer paths to each other (e.g., a tree topology-based path or parallel equal cost paths) before a data packet needs to be routed; hence, a router determines how to forward a packet based on accessing routing information from an internal table. However, proactive protocols suffer the disadvantage of increased overhead in implementing the routing protocol, resulting in reduced convergence time due to movement in the MANET. Consequently, if a mobile router in a MANET moves, the movement causes a change in the routing infrastructure that requires recalculation of routes in accordance with the new topology. Such movement can have even more disruptive effects in routing protocols that calculate multiple paths to a destination. Hence, routing algorithms that fail to ensure rapid convergence based on the recalculated routes will result in a failure of the routing protocol.
Certain proactive routing protocols have attempted to reduce the overhead associated with establishing precise routes within the MANET. For example, a “Fisheye State Routing” (FSR) protocol, described for example in an Internet Draft by Gerla et al., “Fisheye State Routing Protocol (FSR) for Ad Hoc Networks”<draft-ietf-manet-fsr-03.txt>, Jun. 17, 2002, describes a proactive routing protocol where nodes maintain a link state table based on link state advertisement messages received from neighboring nodes: the frequency of distributing link state advertisement messages is limited based on the “scope” of a node, wherein the nodes periodically exchange the information only with their neighbors that are within their “scope” (no flooding). Hence, the link state table of a node has precise and accurate path quality information for nearby nodes within its scope, with progressively less detail of further nodes outside its scope as the distance increases.
Reactive MANET protocols were developed to improve the convergence of MANET protocols, where routing information is acquired only when needed. Examples of reactive protocols include “AODV” as described in an Internet Draft by Perkins et al., “Ad hoc On-Demand Distance Vector (AODV) Routing <draft-ietf-manet-aodv.13>”, Feb. 17, 2003, and “DSR” as described in an Internet Draft by Johnson et al., “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR) <draft-ietf-manet-dsr-10.txt>”, Jul. 19, 2004. Another example of a reactive MANET protocol is IEEE 802.5 source route bridging.
Reactive MANET protocols such as the DSR protocol involve a source MANET host node locating a destination MANET host node by flooding the MANET with a discovery request to locate the destination: if an intermediate mobile host receives the discovery request and does not recognize the destination, the intermediate mobile host will add its network address and will flood the discovery request on its mesh links. Hence, the discovery request includes an explicit hop-by-hop path as it traverses the MANET: if the destination MANET host node is found, a reply is sent to the source MANET host node that includes the explicit hop-by-hop path. Hence, the source MANET host node can send a packet to the destination using strict source routing, where the packet includes a routing header that explicitly specifies the hop-by-hop path to the destination, eliminating the necessity for any further routing protocols.
Hence, strict source routing enables packets to be sent in a MANET network without relying on IP protocols, enabling deployment within layer 2 mesh networks (e.g., Token Ring, IEEE 802.11s, etc.), or layer 3 MANET networks utilizing reactive routing protocols such as DSR or AODV. Another example of strict source routing is illustrated in the form of a reverse routing header as described in U.S. Patent Publication No. US 2004/0117339, published Jun. 17, 2004, the disclosure of which is incorporated in its entirety herein by reference.
Strict source routing, however, suffers from the problem of requiring an explicit source route path within each and every packet: this explicit source route path substantially increases the packet size and reduces efficiency of the network. Moreover, the repeated flooding of the MANET with discovery and reply messages for each and every destination can substantially increase the latency for many applications, and substantially increase traffic within the MANET. Further, any link failure between two nodes in the explicit source route path requires a maintenance (i.e., recalculation) of all the routes that pass along the failed link, resulting in additional flooding of discovery and reply messages that bypass the failed link. Hence, the use of strict source routing reduces communications efficiency due to substantially increased overhead in packets utilizing routing headers, since a separate routing header is required for each hop in the path from a source node to a destination node.
Consequently, a fundamental problem with strict source routing is the associated increase in the size of a data packet, whereas the fundamental problem with proactive routing protocols is the amount of routing information that must be distributed to maintain network integrity (i.e., convergence of network routes) and to permit routing of packets.
A solution to these and other problems is described in the accompanying brief description of the attached drawings and the accompanying description of embodiment(s) of the invention as specified in the appended claims, the description of the embodiment(s) including at least one best mode for carrying out the invention.